package dataStructure.Sort;

import java.util.Arrays;

public class InsertSort {
    /**
     * 把数组分为两个区域,排序区域和未排序区域
     * 每轮从未排序区域中取第一个数放入排序区域中对应的位置
     *
     * @param nums 排序数组
     */
    public static void insertSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            //i左边的是排序区域(不包括i),i右边的是未排序区域
            int toInsert = nums[i];//要插入的数
            for (int j = 0; j < i; j++) {
                if (toInsert < nums[j]) {//这个判断条件要搞明白,插入的时候放在第一个比自己大的数的位置
                    //插入j的位置,数组顺位往后移动一位
                    for (int k = i; k >= j + 1; k--) {
                        nums[k] = nums[k - 1];
                    }
                    nums[j] = toInsert;
                    break;
                }
            }
        }
    }

    public static void insertSortV2(int[] nums) {
        //从位置1开始插入就行,能省去一次操作
        for (int i = 1; i < nums.length; i++) {
            int toInsert = nums[i];//要插入的元素
            int j = i;
            for (; j > 0; j--) {
                if (nums[j - 1] > toInsert) {//左边项大于要插入项,就要右移
                    nums[j] = nums[j - 1];
                } else {
                    //此时位置对了
                    break;
                }
            }

            nums[j] = toInsert;
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{11, 10, 2, 7, 5, 4, 1};
        insertSortV2(nums);
        System.out.println(Arrays.toString(nums));
    }
}
